package org.zjx.data.route.algorithm;

import org.zjx.command.entity.Route;
import org.zjx.command.entity.screen.Address;
import org.zjx.data.route.RouteGraph;

import java.util.*;

/**
 * Dijkstra算法路径查找实现类
 * 实现了PathFindingStrategy接口，使用Dijkstra算法在路由图中查找最短路径
 * 特点：保证找到最短路径，但相比A*算法效率较低
 */
public class DijkstraPathFinding implements PathFindingStrategy {

    /**
     * 节点信息内部类，用于记录路径查找过程中的节点状态
     */
    private static class NodeInfo {
        Address previous;  // 前驱节点位置
        Route route;        // 到达该节点的路由
        int totalTime;      // 从起点到该节点的总耗时(秒)

        NodeInfo(Address previous, Route route, int totalTime) {
            this.previous = previous;
            this.route = route;
            this.totalTime = totalTime;
        }
    }

    /**
     * 查找从起点到终点的最短路径
     * @param graph 路由图数据结构，包含所有位置和路由信息
     * @param start 起点位置
     * @param end 终点位置
     * @return 路径列表(按顺序)，如果不可达则返回null
     */
    @Override
    public List<Route> findPath(RouteGraph graph, Address start, Address end) {
        // 初始化节点信息映射表和优先队列
        Map<Address, NodeInfo> nodeInfoMap = new HashMap<>();
        PriorityQueue<Address> queue = new PriorityQueue<>(
                Comparator.comparingInt(loc -> nodeInfoMap.get(loc).totalTime));

        // 设置起点信息(总耗时为0)
        nodeInfoMap.put(start, new NodeInfo(null, null, 0));
        queue.add(start);

        // 主循环，处理队列中的节点
        while (!queue.isEmpty()) {
            Address current = queue.poll();

            // 到达终点，构建路径并返回
            if (current.equals(end)) {
                return buildPath(nodeInfoMap, end);
            }

            // 遍历当前节点的所有邻接路由
            for (Route route : graph.getRoutesFrom(current)) {
                Address neighbor = route.getEnd();
                int newTime = nodeInfoMap.get(current).totalTime + route.getTime();

                // 如果找到更短路径
                if (!nodeInfoMap.containsKey(neighbor) ||
                        newTime < nodeInfoMap.get(neighbor).totalTime) {

                    nodeInfoMap.put(neighbor, new NodeInfo(current, route, newTime));
                    queue.add(neighbor);
                }
            }
        }

        // 队列为空且未到达终点，表示不可达
        return null;
    }

    /**
     * 根据节点信息构建路径
     * @param nodeInfoMap 节点信息映射表
     * @param end 终点位置
     * @return 从起点到终点的路径列表
     */
    private List<Route> buildPath(Map<Address, NodeInfo> nodeInfoMap, Address end) {
        LinkedList<Route> path = new LinkedList<>();
        Address current = end;

        // 从终点回溯到起点
        while (nodeInfoMap.get(current).previous != null) {
            NodeInfo info = nodeInfoMap.get(current);
            path.addFirst(info.route);  // 添加到路径开头
            current = info.previous;
        }

        return path;
    }
}